import java.util.Arrays;
import java.util.Random;

import static java.lang.Math.max;

public class Main {
    static Random rn = new Random(System.currentTimeMillis());
    public static int getRandomInt(int i){
        return Math.abs(rn.nextInt())%i + 1;
    }

    public void testCustomized(){
        int[][][] test = {{{1}},{{1,2,3,4,5,6,7,8}},{{1},{2},{3},{4},{5},{6}}};

        for(int i = 0; i<test.length;i++){
            testWithArray(test[i]);
        }
    }

    public int[][] generateArray(){
        int m = getRandomInt(50);
        int n = getRandomInt(20);
        int[][] array = new int[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                array[i][j] = getRandomInt(40);
            }
        }
        return array;
    }

    public void test(){
        int[][] array = generateArray();
        testWithArray(array);
    }

    public void testWithArray(int[][] array){
        Solution solution = new Solution();

        int expected = findLargest(array);
        int actual = solution.findLargest(array);
        if(actual != expected){
            String msg = "Test Failed\n";
            msg += "Input:" + Arrays.deepToString(array) + "\n";
            msg += "Expected:" + expected + "\n";
            msg += "Actual:" + actual;
            //System.out.println(msg);
            throw new RuntimeException(msg);
        }
    }

    public int findLargest(int[][] array) {
        int m = array.length;
        int n = array[0].length;

        int[][] result = new int[m][n];
        result[0][0] = array[0][0];
        for(int i=1;i<n;i++){
            result[0][i] = array[0][i]+result[0][i-1];
        }
        for(int i=1;i<m;i++){
            result[i][0] = array[i][0]+result[i-1][0];
        }

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                result[i][j] = max(result[i-1][j], result[i][j-1]) + array[i][j];
            }
        }
        return result[m-1][n-1];
    }

    public static void main(String[] args) {
        try {
            Main main = new Main();
            for (int i = 0; i < 20; i++) {
                main.test();
            }
            main.testCustomized();
        }catch (Exception ex){
            System.out.println(ex.getMessage());
            System.exit(-1);
        }
    }
}
